1. Field of the Invention
The present invention relates to the field of data communications networks. More particularly, the present invention relates to a method and apparatus for implementing a facility within a component of a data communications network that tracks packet flows with a content addressable memory (CAM) for managing and processing the contents of that CAM.
2. The Background
In switched packet data communications systems, packets are received, modified and transmitted by network node devices known as routers, switches and switching routers. Regardless of the nomenclature, such network node devices typically utilize forwarding engines to maintain flow information relating to each related stream of packets. Flow information for a particular packet flow should be maintained in a local memory at the network node while the packet flow is extant on the network. Flow information should be purged from the memory when the packet flow has stopped so that the memory does not become full. For example, if a user on a computer network is contacting a particular web server on the Internet, the communications from that web server to the user constitute a particular xe2x80x9cflowxe2x80x9d. When the user switches to another web server, those communications constitute a different xe2x80x9cflowxe2x80x9d. The information stored by the Forwarding Engine may be used to reconfigure or rewrite a packet so that it is forwarded to the next node in its journey through the data communications network. It may also be used to provide statistical or accounting data, it may also be used for bridging and learning as well as a plethora of other applications. Once the user disconnects from the first web server, that flow is no longer useful and packets will stop coming through the network node device which match that flow. It is that flow information which should be purged eventually.
With the growth in the use of networks such as LANs, (local area networks), WANs (wide area networks), the Internet and corporate intranets, the processing rates of packets through nodes on the networks have increased drastically and need to increase even more in order to meet future anticipated demand for communications speed and volume. Furthermore, the diversity of different flows has increased so that there are drastically more flows to keep track of than there were in the past. Furthermore, flows appear and terminate much more quickly than in the past due to the variety of services available on such networks. Finally, it is becoming more important to be able to gather statistical and accounting information relating to the various flows for network maintenance, design and accounting purposes.
One solution is to keep track of these flows in large tables of Random Access Memory (RAM) or Static RAM (SRAM). Such tables can store forwarding information for packet flows based upon the packet""s Layer 2 and/or Layer 3 information. They can also store statistical information relating to such flows and permit it to be updated frequently. When such a solution is used, the xe2x80x9clearningxe2x80x9d function, whereby portions of new flows are written into the memory, is typically performed by packet processing hardware. This is because of the inherent speed advantage that hardware has over CPU (central processing unit)-processed software solutions. In the learning function the table stored in memory is modified to add information taken from newly detected packet flows. Because the table can be large (having hundreds of thousands of entries or more) and the flow entries may contain hundreds of bits of information, it is desirable to hash the entries based upon a reduced number of the flow bits and therefore scatter the entries pseudo-randomly throughout the table.
Once a Forwarding Table is established, however, it is important to be able to manage it. Even a table with millions of possible entries will eventually become full if no mechanism exists to purge entries every once in awhile. Traditionally, such routines have been executed in software by a CPU associated with the network node device.
A CPU has a limited number of instruction cycles that it may accomplish in a given amount of time. Some of the time the CPU is free to access the Forwarding Table, some of the time it is not free to access the Forwarding Table. Given the speed at which modern network node devices operate, it is simply impractical for a software routine under the control of a CPU to serially access each entry in a Forwarding Table and then act on it. Accordingly, a need exists for a mechanism whereby a large, table of packet forwarding information may be managed quickly by a CPU without causing a significant impact on system throughput or responsiveness.
A hardware search engine facility is provided to allow CPU search and update of a Forwarding Table CAM under the control of software running on the CPU. The hardware search engine provides one or more comparand-mask pairs which allow for a match, exclusion or magnitude comparison on specific entry values and/or the option to ignore or xe2x80x9cdon""t carexe2x80x9d certain bits of the entry. Control registers may be set in software to specify a start address and stop address in the CAM for the search. An indication of valid or invalid entries may be provided as well. Once the search is initiated by software, the search engine will read the entries sequentially starting from the programmed start address. It will perform a compare using the comparand-mask pair and attempt to identify a match. The locations in the CAM which match the search criteria may be put into a CPU-accessible memory. If the memory fills up before it can be read by the software, the search may be halted until the memory is emptied. A programmable action may instead, or in addition, be set to take place in the event of a match. Such programmable actions may include, but are not limited to, marking the entry, deleting the entry, change status bits corresponding to the entry, rewriting some of the entry, and the like.